CDF confidence bands - DKW inequality

2022-03-08 · 2 min read

Overview #

Let's say I have a well known distribution defined by a CDF $F(x)$. I also sample an empirical CDF $F_n(x)$ from a population. Given some confidence parameter, the DKW Inequality bounds how close a random ECDF $F_n(x)$ will be to the true CDF from which the samples are drawn.

Inequality #

The inequality itself states the probability that the Kolmogorov-Smirnov Statistic violates some bound (the K-S statistic is just $||F_n(x) - F(x)||_{\text{max}}$)

Note: there is an extended inequality for a multivariate $F$. The bound changes from $2 e^{(\cdots)}$ to $2k \, e^{(\cdots)}$, where $k$ is the vector dimension.

CDF Confidence Bands #

We can use the DKW Inequality to produce a "band" around our true CDF that must contain our empirical CDF with some confidence probability.

With a failure probability $\alpha$, our sampled ECDF will sit outside the interval

Pros #

1. allows us to contain the entire CDF with a single band value.
2. non-parametric - requires no assumptions about the sample distribution.

Cons #

1. provides weak guarantees at the tails, tighter bounds around the median
2. pointwise approaches (what?) can provide tighter bounds at each individual value
3. non-parametric - provides weaker bounds than others with more assumptions.

Example Bounds #

Links #

1. DKW Inequality (wikiwand)
2. ENS PSL Fact Sheet 1: DKW Inequality
3. On the tight constant in the multivariate DKW Inequality
4. Kolmogorov-Smirnov Statistic (wikiwand)